Fast Discrete Distribution Clustering Using Wasserstein Barycenter with Sparse Support

摘要

In a variety of research areas, the weighted bag of vectors and the histogramare widely used descriptors for complex objects. Both can be expressed asdiscrete distributions. D2-clustering pursues the minimum total within-clustervariation for a set of discrete distributions subject to theKantorovich-Wasserstein metric. D2-clustering has a severe scalability issue,the bottleneck being the computation of a centroid distribution, calledWasserstein barycenter, that minimizes its sum of squared distances to thecluster members. In this paper, we develop a modified Bregman ADMM approach forcomputing the approximate discrete Wasserstein barycenter of large clusters. Inthe case when the support points of the barycenters are unknown and have lowcardinality, our method achieves high accuracy empirically at a much reducedcomputational cost. The strengths and weaknesses of our method and itsalternatives are examined through experiments, and we recommend scenarios fortheir respective usage. Moreover, we develop both serial and parallelizedversions of the algorithm. By experimenting with large-scale data, wedemonstrate the computational efficiency of the new methods and investigatetheir convergence properties and numerical stability. The clustering resultsobtained on several datasets in different domains are highly competitive incomparison with some widely used methods in the corresponding areas.